package Tree;

import sun.reflect.generics.tree.Tree;

import java.util.Stack;

/**
 *  题目 ： 二叉搜索树的中序后继
 *  题目详述 ：
 *  给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
 * 节点p的后继是值比p.val大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。
 *
 */
public class InorderSuccessor {
    /**
     * 核心思想 ：
     * 由于需要获取二叉搜索树中某个节点的中序后继，考虑到二叉搜索树中中序后继必然是为当前节点的右子节点
     * ===》 即，通过设置一个标志位flag，来标记是否已经遍历到所传入的节点；
     * @param root
     * @param p
     * @return
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        /**
         * 时间复杂度 ：O（n）
         * 分析 ：由于需要中序遍历二叉树中的所有节点，所以我们会需要花费的时间复杂度为O（n）；
         * 同时，空间复杂度也与二叉树中的节点数相关，即需要在Stack栈中存储一党的节点数；
         */
//        Stack<TreeNode> stack = new Stack<>();
//        Boolean flag = false;
//        TreeNode node = root;
//        // 对于二叉树进行中序遍历 --- 迭代逻辑
//        while(node != null || !stack.isEmpty()){
//            while(node != null){
//                stack.push(node);
//                node = node.left;
//            }
//            node = stack.pop();
//
//            // 核心代码 ：通过flag标志位，来判断是否已经便利到所传入的节点；
//            if(flag){
//                break;
//            }
//            else if (p == node){
//                flag = true;
//            }
//
//            node = node.right;
//        }
//        return node;


        /**
         * 思路 ：
         * （1）根节点开始，将根节点的值 和 所传入节点的值进行比较，
         * （2）若是根节点的值小于所传入节点的值的话，即需要将根节点变化为其右子节点，
         * （3）若是当前根节点的值是大于所传入节点的值的话，需要去遍历当前根节点的左子树，去获取其是否存在更小的节点；
         * （4）若是当前根节点的值 是小于所传入节点的值的话，即需要将node节点指向node节点的右子节点；
         * 注意 ：
         * 二叉搜索树的右子节点必然是大于根节点的；同时其左子节点也是必然小于根节点的；
         * 问题 ：为什么需要去遍历已经满足条件的根节点的左子树？
         * 回答 ：
         * （1）由于根节点的值是大于所传入节点的值，去遍历左子树（左子树中的所有节点都是小于目前的根节点的）；
         * （2）看当前根节点的左子树中是否存在 比根节点小，但是同时又是比所传入节点值大的节点；
         */
        TreeNode node = root;
        TreeNode minNode = null;
        while(node != null){
            if(node.val > p.val){
                minNode = node;
                node = node.left;
            }
            else {
                node = node.right;
            }
        }
        return minNode;
        /**
         * 时间复杂度 ：由于通过根节点和所传入节点的值 相互之间进行判断，即时间复杂度为O（h），h为二叉搜索树的深度；
         * 空间复杂度 ：O（1）
         */
    }
}
